package com.future;
/*
 * com.future CO.,ltd.
 */

/**
 * Description: 大厂刷题班第5个视频（72. 编辑距离）
 * 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
 * <p>
 * 你可以对一个单词进行如下三种操作：
 * <p>
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：word1 = "horse", word2 = "ros"
 * 输出：3
 * 解释：
 * horse -> rorse (将 'h' 替换为 'r')
 * rorse -> rose (删除 'r')
 * rose -> ros (删除 'e')
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/edit-distance
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author: future
 * @Date:2022/3/27:14:22
 */
public class Solution_72_minDistance {

    public static void main(String[] args) {
        // String word1 = "intention", word2 = "execution";
        String word1 = "", word2 = "a";
        System.out.println(minDistance(word1, word2));
    }

    /**
     * 可参考截图 class05.Solution_72_minDistance.jpg
     * d---delete删除的代价
     * a---add添加的代价
     * r---replacet替换的代价
     * <p>
     * dp[i][j]表示
     * s1从0...(i-1)编辑成s2从0...(j-1)
     * 最少代价（注意：i,j表示长度，不是下标）
     * 可能性：
     * ========1、dp[i-1]+delete
     * 最后一个字符多余
     * eg1:s1=abcde , s2=abcd
     * s1的最后一个多余的
     * eg2:s1=abkfe , s2=abcf
     * 先把s1的前i-1变成abcf,则s1又变成了s1=abcfe,s2=abcf，这里s1最后一个多余
     * ========2、dp[i][j-1]+add
     * 先把s1的整体对应上s2的j-1的整体，然后把s2的最后一个字符add上s1
     * eg1:s1=abtc,s2=abkcd
     * 先把s1=abtc变成s1=abkc,然后s1添加s2的最后一个字符变成s1=abkcd
     * ========3、s1[i-1]=s2[j-1],dp[i-1][j-2]
     * s1的第i-1位置字符等于s2的第j-1位置字符，只需要保证s1[0...i-2]=s2[0....j-2]就可以了
     * ========4、s1[i-1]!=s2[j-1],dp[i-1][j-1]+r
     * s1第i-1字符与s2第j-1不相等，就替换
     */
    public static int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null) {
            return 0;
        }
        char[] str1 = word1.toCharArray();
        char[] str2 = word2.toCharArray();
        int N = str1.length + 1;
        int M = str2.length + 1;
        int[][] dp = new int[N][M];
        for (int i = 1; i < N; i++) {
            /**
             * 当s2长度为0时，即s2=""时
             * 长度为i的s1需要几步变成s2
             * 只能移除
             * eg:s1=abc,s2="";
             * s1移除成s2需要的代价为4*dc
             */
            dp[i][0] = 1 * i;
        }
        for (int j = 1; j < M; j++) {
            /**
             * 当s1长度为0时，即s1=""时
             * 长度为0的s1需要几步变成长度为i的s2
             * 只能添加
             * eg:s1="",s2="abc";
             * s1添加成s2需要的代价为4*ic
             */
            dp[0][j] = 1 * j;
        }
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < M; j++) {
                /**
                 * s1前i-2跟s2前j-2都相等，第i-1相等代价就为0，否则需要替换成s2的第j-1位字符，代价为rc
                 * eg1:第i-1和j-1不相等，需要把'd'替换成‘c’
                 * s1=...abcd...
                 * s2=...abcc...
                 * eg2:第i-1和j-1相等，不需要任何操作，代价为0
                 * s1=...abcd...
                 * s2=...abcd...
                 */
                int v1 = dp[i - 1][j - 1] + (str1[i - 1] == str2[j - 1] ? 0 : 1);
                /**
                 * s1前i-1跟s2前j-2都相等，则s1少一位，需要把第i-1为insert进来，代价为ic
                 * eg:
                 * s1=abc...
                 * s2=abcd...
                 * 则s1需要在c后面insert一个‘d’字符变成s1=abcd...
                 */
                int v2 = dp[i][j - 1] + 1;
                /**
                 * s1 前i-2跟s2前j-1位都相等，需要把s1的i-1位置移除delete,代价为dc
                 * eg:
                 * s1=abcd...
                 * s2=abc...
                 * 则s1需要把d移除变成abc
                 */
                int v3 = dp[i - 1][j] + 1;
                dp[i][j] = Math.min(Math.min(v1, v2), v3);
            }
        }
        return dp[N - 1][M - 1];
    }
}
